'''
Created on 2010-3-3

@author: Administrator
'''
import sys
from jolly.datastructures.Tree import Tree
from jolly.datastructures.LinkedList import LinkedList

class GeneralTree(Tree):
    '''
    A general tree implemented using a linked list of subtrees.
    '''


    def __init__(self, key):
        '''
        (GeneralTree, Object) -> None
        Constructs a general tree with the given object at its root.
        '''
        super(GeneralTree, self).__init__()
        self._key=key
        self._degree=0
        self._list=LinkedList()
    
    def purge(self):
        '''
        (GeneralTree) -> None
        Purges this general tree.
        '''
        self._list.purge()
        self._degree=0
    
    def getIsEmpty(self):
        '''
        (GeneralTree) -> bool
        Returns false always.
        '''
        return False
    
    def getIsLeaf(self):
        '''
        (GeneralTree) -> bool
        Returns true if this general tree is a leaf.
        '''
        return self._degree==0
    
    def getDegree(self):
        '''
        (GeneralTree) -> int
        Returns the degree of this general tree node.
        '''
        return self._degree
    
    def getKey(self):
        '''
        (GeneralTree) -> Object
        Returns the key in this general tree node.
        '''
        return self._key
    
    def getSubtree(self, i):
        '''
         (GeneralTree) -> Object
        Returns the specified subtree of this general tree node.
        '''
        if i<0 or i>=self._degree:
            raise IndexError
        ptr=self._list.head
        for j in xrange(i):
            ptr=ptr.next
        return ptr.datum
    
    def attachSubtree(self, t):
        '''
         (GeneralTree, GeneralTree) -> None
        Attaches the given general tree as a subtree
        of this general tree node.
        '''
        self._list.append(t)
        self._degree+=1
    
    def detachSubtree(self, t):
        '''
        (GeneralTree, GeneralTree) -> GeneralTree
        Detaches and returns specified general tree
        from this general tree node.
        '''
        self._list.extract(t)
        self._degree-=1
        return t
    
    def _compareTo(self, obj):
        '''
        (GeneralTree, GeneralTree) -> int

        Compares this general tree with the given general tree.
        '''
        assert isinstance(self, obj.__class__)
        raise NotImplementedError
    
    @staticmethod
    def main(*argv):
        "GeneralTree test program."
        print GeneralTree.main.__doc__
        gt = GeneralTree('A')
        gt2 = GeneralTree('B')
        gt.attachSubtree(gt2)
        gt.attachSubtree(GeneralTree('C'))
        gt.attachSubtree(GeneralTree('D'))
        gt.attachSubtree(GeneralTree('E'))
        gt2.attachSubtree(GeneralTree('F'))
        Tree.test(gt)
        return 0

if __name__ == "__main__":
    sys.exit(GeneralTree.main(*sys.argv))
        